LeetCode Merge k Sorted Lists 题解
思路一
使用之前合并两个lists的方法,重复调用k次
思路二
从lists中找到前面一个元素最小的list,将这个list的首个node加入到要返回的list中的末尾中去,不断循环,直到lists中所有的node都取出来为止
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int getMinIndex(vector<ListNode*>& lists)
{
int minVal = 2147483647 ,minIndex = -1;
for(int i=0;i<lists.size();i++)
{
if(lists[i] != NULL && minVal > lists[i]->val)
{
minVal = lists[i]->val;
minIndex = i;
}
}
return minIndex;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res =NULL, *p =NULL;
int len = lists.size();
if(len == 0) return NULL;
int ind = getMinIndex(lists);
while(ind != -1)
{
// node 移植
if(res ==NULL)
{
res = p = lists[ind];
}
else
{
p->next = lists[ind];
p = p->next;
}
// 删除list中的node
lists[ind] = lists[ind]->next;
ind = getMinIndex(lists);
}
return res;
}
};
思路三
将所有的node都加入到一个最小堆中,不断从这个最小堆中取出最小的一个node形成一个list
1 | /** |
思路四
归并排序的思想,不断拆分成两个list的合并,最后合并的次数只有logk次,所以整体的时间复杂为O(n*logk)
更多LeetCode题解,欢迎查看我的GitHub项目